/*
 * @lc app=leetcode.cn id=1585 lang=typescript
 *
 * [1585] 检查字符串是否可以通过排序子字符串得到另一个字符串
 */

// @lc code=start
function isTransformable(s: string, t: string): boolean {
  // s 字符串中每个数字的下标
  const pos: number[][] = new Array(10).fill(0).map(() => []);
  for (let i = 0; i < s.length; i++) {
    pos[Number(s[i])].push(i);
  }

  // 检查 t 中每个数字是否可以通过排序 s 中的数字得到
  for (let i = 0; i < t.length; i++) {
    const num = Number(t[i]);
    // 数字不在 s 中
    if (pos[num].length === 0) {
      return false;
    }
    // 数字在 s 中的下标
    const p = pos[num].shift();
    // 检查当前数字前在 s 中是否还有比它小的数字
    for (let j = 0; j < num; j++) {
      if (pos[j].length && pos[j][0] < p) return false;
    }
  }

  return true;
}
// @lc code=end
